import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/2 9:48
 * @description 思路：排序并用boolean数组，确定重复的数字前面先取
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, 2, 2};
        solution.subsetsWithDup(nums);
    }
    List<Integer> t = new ArrayList<>();
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        backtrack(false, 0, nums);
        return ans;
    }
    public void backtrack(boolean choosePre, int cur, int[] nums) {
        if (cur == nums.length) {
            ans.add(new ArrayList<>(t));
            return;
        }
        backtrack(false, cur + 1, nums);
        if (cur > 0 && nums[cur] == nums[cur - 1] && !choosePre) {
            return;
        }
        t.add(nums[cur]);
        backtrack(true, cur + 1, nums);
        t.remove(t.size() - 1);
    }
}
